Information transmitted over a communication channel, including a tape recorder, is generally received as a combination of the original information signal and a noise component. Integrity of the information content is almost entirely preserved when the signal to noise ratio of the system is large. Accordingly, refinements in design and realization of the appropriate hardware can increase the probability of error-free transmission, theoretically up to the limits imposed by the channel itself. In order to minimize the effect of intrinsic channel limitations, various techniques are employed which ultimately require a compromise between bandwidth and information transfer rate. Various limitations imposed on the channel bandwidth, information rate, and the degree of complexity of receiving and transmitting apparatus contribute to a probable error rate.
Although redundancy is a common element among these techniques, mere repetition exacts a heavy penalty in transmission rate. For example, a single repetition reduces the information rate 50 percent and a second repetition (to implement majority logic) reduces the information rate by 662/3 percent. Other means for assuring message integrity have employed sophisticated coding techniques which permit the detection, location, and correction of errors. Among the desiderata of these coding techniques are high information rate and a capability of correcting multiple errors within any given codeword of transmitted data.
In this context a codeword of n elements results from encoding operations performed upon the elements of the original data comprising k elements to yield an encoded word ("codeword") of information having k information elements and n-k check elements. The encoded redundancy in the form of n-k check elements is then available during the decoding operations to detect and correct errors in the codeword (including all information and check elements) up to some limit or merely to detect errors up to some larger limit.
Many such codes, having distinct mathematical properties, have been studied and mathematically efficient encoding and decoding procedures have been devised, but reduction to practice with concomitant efficiency requires a special purpose computer. For example, certain classes of codes are founded on association of each information element of a codeword with an element of a Galois field. Very briefly, the Galois field is a finite field defined by a field generator, the elements of which field may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. If the coefficients are presented in serial form with the most significant coefficient first, field elements can alternatively be considered polynomials in z, where z.sup.-1 is the delay operator.
Encoding is done by adding redundant elements to the source data elements in order to make the resulting codeword satisfy prescribed parity checks. Each prescribed parity check is formed as a weighted sum of the elements in the codeword. The result of each prescribed parity check upon decoding is generally referred to as a syndrome. In the absence of errors for a linear code, all the syndromes are zero, meaning that the weighted sum of the elements forming each parity check is zero, and the presence of errors is recognized by a non-zero syndrome. In the absence of errors for the coset code of a linear code, all the syndromes have some prescribed non-zero values, and the presence of errors is recognized by departures from the prescribed non-zero values. Cyclic codes, such as Reed-Solomon codes, are a subset of linear codes. The elements of a cyclic codeword can be associated with coefficients of a codeword polynomial. The formation of parity checks can be equated with the taking of a remainder upon division of the codeword polynomial by the code generator polynomial for the code. The locations of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. An encoder and decoder are, therefore, required which have the capability of performing Galois field arithmetic.
The same parity check circuit may be used for encoding and decoding, that is, for generating parity and syndrome bytes. In encoding, the data may be taken in data blocks and associated with coefficients of what may be called a data polynomial. The formation of parity checks can be performed identically as in the case of codewords to determine whether or not the data polynomial itself is divisible by the code generator polynomial. If not, the remainder is added to the data polynomial to form the codeword polynomial. Thus the remainder, whether parity or syndrome bytes, may be referred to as a parity check. For the same reasons, the term "data block bits" refers to bits corresponding to the coefficients of either the data polynomial or the codeword polynomial, as the case may be.
Of the error correcting codes, a particular class of such codes, separately described by Bose, Chaudhuri and Hocquenhem (thus "BCH" codes), are capable of multiple error correction. Special cases of such codes are the Reed-Solomon (RS) codes with respect to which the present invention will be described.
The Berlekamp patent includes a review of the salient aspects of coding theory, applicable to nonbinary BCH codes in general and to RS codes in particular. As a general reference, Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968), is recommended. In a binary realization, such codes may be regarded as having three principal positive integer parameters, n, m, and t, where n is the total length in m-bit characters of a word of encoded information, n=2.sup.m -1, and t is the error correcting capability of the code. Assuming no fewer than 2t redundant characters or check characters such a codeword is capable of providing sufficient informational redundancy to detect and correct any set of t or fewer independent errors within the codeword of encoded information, or to correct any set of 2t or fewer independent erasures. An erasure may be defined as an error of known location within the received codeword.
The properties of an algebraic finite field may be summarized briefly. For the purposes of the present invention, a field may be informally defined as a set of elements including the null element, 0, and the unit element, 1, upon which are defined operations of addition, multiplication and division. Addition and multiplication are associative and commutative, and multiplication is distributive with respect to addition. Every element of the field has a unique negative such that the negative of a given element summed with that given element itself yields the null or 0. Further, every nonzero element has a unique reciprocal such that the product of such an element with its reciprocal yields the unit element, 1. The elements comprising the field may be considered symbolic representations of binary or ternary or q-ary numbers. The description of the invention will be understood best in terms of a field of characteristic two.
The general finite field is called the Galois field and is specified by two parameters; a prime p, and an integer m, whereby GF(p.sup.m) describes a unique finite field (the Galois field of order p.sup.m) having p.sup.m elements. In such a field all operations between elements comprising the field yield results which are again elements of the field. For example, the operation of addition carried out on elements of the finite field GF(2) is defined, modulo 2, according to relations which do not admit of a "carry". Thus, the binary addition tables are: 0+1=1+0=1 and 0+0=1+1=0. Arithmetically, this is a "carry-less" addition, sometimes referred to as half addition and more commonly denoted as the exclusive-OR (XOR). It is apparent that absence of a carry thereby limits the magnitude of the resulting sum to the finite field.
The mathematical basis of Reed-Solomon codes and decoding thereof, as discussed in greater detail in Chapter 10 of Algebraic Coding Theory is as follows:
Let .alpha..sup.b be a primitive element in GF(2.sup.m). The code generator polynomial is defined by ##EQU1## where b, d, f and i are integers and d is the code's designed distance. The block length of the Reed-Solomon code is n=2.sup.m -1. The codewords consist of all polynomials of degrees less than n which are multiples of g(x).
Let C(x) be the transmitted codeword, ##EQU2## If the channel noise adds to this codeword, the error pattern ##EQU3## then the received word is ##EQU4##
The received codeword may be passed through a re-encoder (also known as a syndrome generator) which produces as its output the remainder of the polynomial division
S(x)=Remainder [R(x)/g(x)]=Remainder [E(x)/g(x)] from which may be derived the weighted power-sum symmetric functions defined by EQU S.sub.ib =S(.alpha..sup.ib)=E(.alpha..sup.ib)
from which may be derived the location and nature of any errors, and appropriate corrections can be made, all as described in the Berlekamp patent.
In order to perform such error correction, it is necessary to encode the source data into codewords and to identify errors in the recovered codewords. This is done by adding parity bytes to the bytes of source data to generate codewords satisfying certain parity checks and by identifying departures from such parity checks in the recovered codewords as syndromes. Such are the functions performed by the present invention for byte-parallel, bit-serial data recorded on multi-track instrument recorders. A particular embodiment actually constructed was for an available 14-channel digital instrumentation tape recorder.
The present invention utilizes the properties of an algebraic finite field as stated above, namely, that addition and multiplication are associative and commutative, and multiplication is commutative with respect to addition. This permits each of the coefficients of the data and codeword polynomials to be separately divided to produce remainders, which may then be added together to form the remainders for the division of the entire polynomial.
Such properties have been utilized in the prior art. Conventionally, data and codewords have been presented byte-serially, bit serially, with the most significant bytes and bits presented first. That is, C.sub.n-1 is presented first in bit order, then C.sub.n-2 on down to C.sub.0. It is well known to accumulate the bits of each coefficient in a shift register and then divide each coefficient by the code generator polynomial in an appropriate Galois field and appropriately combining the remainders in respect to each coefficient to produce a block parity check. This prior art system thus operates on data byte-serial, bit-parallel.